# 最大单词长度乘积： https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

class Solution:
    def maxProduct(self, words: list) -> int:
        """
            暴力解法
        """
        def compare1(s1, s2):
            for c1 in s1:
                for c2 in s2:
                    if c1 == c2: 
                        return False          
            return True

        rst = 0
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if compare(words[i], words[j]):
                    rst = max(rst, len(words[i]) * len(words[j]))

        return rst


# 优化暴力解法的compare()
def compare(s1, s2):
    """ 使用计数排序 """
    cnt = [0] * 26
    for c in s1: cnt[ord(c) - ord("a")] = 1
    for c in s2: 
        if cnt[ord(c) - ord("a")] == 1:
            return False
            
    return True


# 位运算bit位优化
def compare(s1, s2):
    """ 使用 bit位运算来代替 数组计数，节省空间
        通过 左移运算符， 和 或运算符，使 bitMask该位置表示字符存在
    """
    bitMask1 = 0
    bitMask2 = 0
    for c in s1: bitMask1 |= 1 << (ord(c) - ord("a"))
    for c in s2: bitMask2 |= 1 << (ord(c) - ord("a"))
    
    return bitMask1 & bitMask2 == 0


# 因为 暴力破解， 各元素之间都需要比较。。 所以预先求出 各元素的 bit位表示， 加快效率，消耗空间
# 可以通过，不会超时
class Solution:
    def maxProduct(self, words: list) -> int:
        """
            暴力解法
        """
        rst = 0
        bitList = []
        for i in range(len(words)):
            bitMask = 0
            for c in words[i]: bitMask |= 1 << (ord(c) - ord("a"))
            bitList.append(bitMask)

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if bitList[i] & bitList[j] == 0:
                    rst = max(rst, len(words[i]) * len(words[j]))

        return rst


# 还可以 继续优化 ，比如 eg  egegeg 他们的 bit位表示是一样的， 可以使用map 记录最大的长度，最后 双循环 map